{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a6868936",
   "metadata": {},
   "source": [
    "## 广度优先遍历（BFS=Breadth First Search）\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f568b8b",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "> 参照算法之美的bfs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d00e4212",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 3, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "# python\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "import queue\n",
    "_author_ = 'yjiedu'\n",
    "\n",
    "# 定义链表用于存储邻接表\n",
    "\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=None, next=None) -> None:\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "# 定义无向图\n",
    "class Graph:\n",
    "    def __init__(self, V: int = 0) -> None:\n",
    "        self.V = V  # 顶点个数\n",
    "        self.linkedList = []\n",
    "        for _ in range(V):  # 初始化所有顶点邻接表的表头\n",
    "            self.linkedList.append(ListNode(None))\n",
    "\n",
    "    # 添加边：把边两边顶点分别加入彼此的邻接表中，顶点的下标惟一确定顶点的邻接表\n",
    "    def addEdge(self, s: int, t: int) -> None:\n",
    "        # 把t放置在s链表的尾部\n",
    "        reader = self.linkedList[s]\n",
    "        while reader.next:  # 找到链表尾部\n",
    "            reader = reader.next\n",
    "        reader.next = ListNode(val=t)\n",
    "        # 把s放置在t链表的尾部\n",
    "        reader = self.linkedList[t]\n",
    "        while reader.next:  # 找到链表尾部\n",
    "            reader = reader.next\n",
    "        reader.next = ListNode(val=s)\n",
    "\n",
    "# 给定图G，开始端点s， 终点t，每个边的距离都为1，输出s到t的最短路径（不止一个）\n",
    "\n",
    "\n",
    "def bfs(G: Graph, s: int, t: int) -> List[int]:\n",
    "    Vnum = G.V  # 顶点数目\n",
    "    linkedList = G.linkedList\n",
    "    visits = [0]*Vnum\n",
    "    preV = [-1]*Vnum  # 第一个顶点的前置顶点为-1\n",
    "    q = queue.Queue()\n",
    "    q.put(s)  # 放置开始节点到队列\n",
    "\n",
    "    flag = True  # 找到目标点的标志位\n",
    "    while (not q.empty()) and flag:\n",
    "        pos = q.get()  # 从队列中取出一个顶点\n",
    "        # 遍历当前顶点的相邻顶点\n",
    "        if visits[pos] == 0:  # 当前顶点没有被访问过\n",
    "            visits[pos] = 1 # 设置该顶点已经被访问\n",
    "            reader = linkedList[pos]\n",
    "            while reader.next:  # 遍历当前顶点的邻接表\n",
    "                if visits[reader.next.val] == 1: # 跳过已经访问过的顶点\n",
    "                    reader = reader.next\n",
    "                    continue\n",
    "                preV[reader.next.val] = pos  # 存储前置顶点\n",
    "                # visits[reader.next.val] = 1\n",
    "                if reader.next.val == t:  # 找到目标顶点\n",
    "                    preV[t] = pos\n",
    "                    flag = False  # 找到\n",
    "                    break\n",
    "                else:\n",
    "                    q.put(reader.next.val)  # 把相邻节点加入队列\n",
    "\n",
    "                reader = reader.next\n",
    "\n",
    "    # 输出s到t的最短路径\n",
    "    path = []\n",
    "    i = t\n",
    "    while i != s:\n",
    "        path.append(i)\n",
    "        i = preV[i]\n",
    "    path.append(s)\n",
    "\n",
    "    return path[::-1]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    G = Graph(V=8)\n",
    "    edges = [[0, 1], [1, 2], [0, 3], [1, 4], [2, 5],\n",
    "             [3, 4], [4, 5], [4, 6], [5, 7], [6, 7]]\n",
    "    for edge in edges:\n",
    "        G.addEdge(edge[0], edge[1])\n",
    "\n",
    "    path = bfs(G, 0, 6)\n",
    "    print(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78dde167",
   "metadata": {},
   "source": [
    "### 二叉树的层序遍历\n",
    "> [102. 二叉树的层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75c9c6b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        preLevel = [root]\n",
    "        res = []\n",
    "        res.append([root.val])\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            tmp = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    tmp.append(node.left.val)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    tmp.append(node.right.val)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "524ec3e6",
   "metadata": {},
   "source": [
    "### 二叉树的锯齿遍历\n",
    "> [103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4370b157",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        preLevel = [root]\n",
    "        res = [[root.val]]\n",
    "\n",
    "        flag = False # 反序标志位\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            vals = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    vals.append(node.left.val)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    vals.append(node.right.val)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                if flag:\n",
    "                    res.append(vals)\n",
    "                else:  # 反序\n",
    "                    res.append(vals[::-1])\n",
    "                flag = not flag\n",
    "\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9f91224",
   "metadata": {},
   "source": [
    "###  二叉树最小深度\n",
    "> [111. 二叉树的最小深度 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "94bcdd4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        depth = 1\n",
    "        preLevel = [root]\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if not node.left and not node.right:\n",
    "                    return depth\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                preLevel = recuLevel\n",
    "                depth += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80fc4f88",
   "metadata": {},
   "source": [
    "### 二叉树根节点到叶子节点的路径和\n",
    "> [112. 路径总和 - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce5f4d7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        preLevel = [root]\n",
    "        lastVals = [root.val]\n",
    "        while True:\n",
    "            recuLevel = []\n",
    "            vals = []\n",
    "            for i,node in enumerate(preLevel):\n",
    "                if not node.left and not node.right: # 叶子节点\n",
    "                    sumTmp = lastVals[i]\n",
    "                    if sumTmp==targetSum:\n",
    "                        return True\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                    vals.append(node.left.val+lastVals[i])\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "                    vals.append(node.right.val+lastVals[i])\n",
    "            if recuLevel:\n",
    "                lastVals=vals\n",
    "                preLevel = recuLevel\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return True if targetSum in lastVals else False"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
